/*
 * boggle.cpp
 *
 *  Created on: Aug 13, 2012
 *      Author: jh238d
 */

#include <iostream>
#include <string>
#include "Trie.cpp"
#include <fstream>
#include <hash_set>
using namespace std;

class Boggle {
	private:
	const static int N = 5;
	hash_set<string> m_words;

	public:
	Boggle(){
	}

	void dfs(string cur, char cs[][N], int i, int j, bool used[][N], Trie *trie){
		if(i<0||i>N-1||j<0||j>N-1||used[i][j]) return;
		string next = cur + cs[i][j];
		used[i][j]=true;
		if(!trie->searchPattern(next)) {
			used[i][j] = false;
			return;}
		if(trie->searchWord(next)&&m_words.find(next)==m_words.end()){
			m_words.insert(next);
			cout<<next<<endl;
		}

		for(int m = -1; m <= 1; m++)
			for(int n = -1; n <= 1; n++)
			{
				if(m==0&&n==0) continue;
				dfs(next, cs, i+m, j+n, used, trie);
			}
		used[i][j] = false;
	}

	void run(string str[]){
		char cs[N][N] = {'A','E','B','O','F', 'T','S','U','V','W', 'R','F','O','E','G', 'R','S','O','F','I', 'P','Q','W','R','E'};
		bool used[N][N] = {false};
		m_words.clear();

		Trie* trie = new Trie();
		ifstream myReadFile;
		 myReadFile.open("text.txt");
		 if (myReadFile.is_open()){
			while(!myReadFile.eof()){
				string word;
				myReadFile >> word;
				if(word.length()>0)
					trie->addWord(word);
			}
		 }

		 for(int i=0; i<N;i++){
			 for(int j=0; j<N; j++){
				 dfs("",cs, i, j, used, trie);
			 }
		 }
		 cout << m_words.size() << endl;
	}

};

/*int main(){
	string str[] = {"AEBOF", "TSUVW", "RFOEG", "RSOFI", "PQWRE"};
	Boggle* b = new Boggle();
	b->run(str);
	return 0;
}*/




